\begin{section}{Desarrollo}
%~ \par \noindent
%~ Hablar de la clase CanionWarp, de la separaci\'on de c\'odigo (una especie de modularizaci\'on).

\begin{subsection}{General}
 En general sobre la implementaci\'on se decidi\'o realizar un c\'odigo modularizado para facilitar la comprensión y utilización. Los m\'odulos creados son Defs.h, Vector, Matriz y Sistemas. 
 
\begin{itemize}
	\item \textbf{defs.h} se encuentran las definiciones b\'asicas utilizadas y se incluyen las bibliotecas a utilizar.
	\item \textbf{vector} distancia euclideana entre dos vectores, swap entre dos posiciones del vector, generar un vector con valores double de forma random, mostrar un vector por pantalla.
	\item \textbf{matriz} multiplicaci\'on entre dos matrices, generar una matr\'iz con valores double de forma random, mostrar una matr\'iz por pantalla.
	\item \textbf{sistemas} contiene las diferentes operaciones que involucran matrices y vectores a la vez. Algunas de estas operaciones se explicar\'an en lo que resta del informe. Algunas de las \\operaciones son: multiplicar una matr\'iz por un vector, multiplicar una matr\'iz por una matr\'iz diagonal, backward substitution, forward substitution, c\'alculo de la matr\'iz de Hilbert de tamaño n, descomposici\'on LU, descomposici\'on PLU con pivoteo escalado, b\'usqueda de matr\'iz de disparo.
	\item \textbf{canionWarp} la clase realizada para representar el funcionamiento de un cañon warp.
 \end{itemize} 
\end{subsection}

\begin{subsection}{Estrategias de Ataque y Defensa}
\paragraph{}
Para que el enemigo no pueda calcular la posici\'on propia de manera sencilla se pens\'o que sería adecuada una matriz de disparo que fuera díficil de invertir. 
De la misma forma tambi\'en se di\'o por sentado que el atacante utilizar\'ia una transformaci\'on que se comportar\'ia de manera similar.
\paragraph{}
Analizada esta situaci\'on se procedi\'o a investigar m\'etodos estables para analizar los resultados de los disparos del contricante. 
Los m\'etodos usados a la hora de la codificaci\'on fueron seleccionados por poseer estas caracter\'isticas.
\paragraph{}
Aclarado estos aspectos se presentan a continuaci\'on de manera m\'as concreta los métodos utlizados para el ataque y la defensa:

\begin{subsubsection}{Ataque}
\paragraph{}
En el primer turno no se posee informaci\'on alguna del enemigo, por lo que se decidi\'o tomar como posici\'on enemiga un vector random y disparar a esa posici\'on.
\paragraph{}
A partir del segundo turno se cuenta con la matriz de disparo enemiga y su impacto del turno anterior. 
Dada esta informaci\'on, fue necesario resolver el siguiente sistema:

\begin{equation}
matriz\_enemiga \; * \; posicion\_enemiga \, = \, impacto\_enemigo
\end{equation}
\paragraph{}
Se decidi\'o utilizar la t\'ecnica de pivote escalado para disminuar la inestabilidad num\'erica en la resoluci\'on. Adem\'as con esta t\'ecnica siempre puede encontrarse una descomposici\'on de la matr\'iz.

\paragraph{}
\textbf{Pivoteo Escalado}
\par
Esta t\'ecnica de pivoteo es una variaci\'on del pivoteo parcial. Se elije en cado paso como pivote el elemento con mayor peso relativo respecto a los elementos de la fila.
\newpage
\begin{enumerate}
    \item Buscar el m\'aximo valor en m\'odulo de cada fila. \\
        maximos[$i$] $=$ $\displaystyle \max_{j = 1, \dots, n}{|a_{ij}|}$
    \item Para cada columna $j$ 
    \begin{enumerate}
        \item Dividir cada elemento de la columna en valor absoluto por el m\'aximo de la fila y quedarse con el m\'aximo, y ese ser\'a el pivote. \\
        pivote[$j$] $=$ $p$ $=$ $\displaystyle \max_{i = j, \dots, n}{\displaystyle \frac{|a_{ij}|}{maximos[i]}}$
        \item Intercambiar fila $j$ con fila $p$ en la matr\'iz $A$.
        \item Intercambiar fila $j$ con fila $p$ en $b$.
        \item Realizar el paso de eliminaci\'on gaussiana normalmente ahora que el pivote deseado esta ubicado en $A[j][j]$.
    \end{enumerate}    
\end{enumerate}

\end{subsubsection}
	
\begin{subsubsection}{Defensa}
\paragraph{}
Se decidi\'o utilizar para atacar la matriz de Hilbert, dado que es una matriz conocida y que cumple las propiedades deseadas para el disparo, ya que es inversible y a su vez es dificil de invertir, entre otras propiedades.
 $$ Hilbert_{(i,j)} = \frac{1}{i+j-1}$$ 
 
\paragraph{}
Al generar esta matríz se tuvo en cuenta que en la definición los subíndices comienzan desde $1$ y no desde $0$, por lo tanto, la matríz quedaría definida como 
$$ Hilbert_{(i,j)} = \frac{1}{(i+1)+(j+1)-1} = \frac{1}{i+j+1}$$ 
	
\begin{center}
$ H_n = \begin{pmatrix} 
   \displaystyle 1 & \displaystyle \frac{1}{2} & \ldots & \displaystyle \frac{1}{n} \\ \\
   \displaystyle \frac{1}{2} & \displaystyle \frac{1}{3} & \ldots & \displaystyle \frac{1}{n+1} \\ \\
   \vdots & \vdots & \ddots & \vdots \\ \\
   \displaystyle \frac{1}{n} & \displaystyle \frac{1}{n+1} & \ldots & \displaystyle \frac{1}{2n-1} \end{pmatrix} $
\end{center}

Su n\'umero de condici\'on en la norma euclideana $||\bullet||_2$ para diferentes valores de $n$ es:

\begin{center}
    \begin{tabular}{|c|c|}
    \hline
    $n$ & $K(H_n)$ \\
    \hline
    $10$ & $1.6$ $10^{13}$ \\
    $20$ & $2.45$ $10^{28}$ \\
    $40$ & $7.65$ $10^{58}$ \\
    \hline
    \end{tabular}
\end{center}

\paragraph{}
El n\'umero de condici\'on es grande y crece crece muy rapidamente, lo cual dificulta el c\'alculo de la posici\'on correcta al contrincante.

\end{subsubsection}

\end{subsection}

\begin{subsection}{Clase CanionWarp}
Para poder resolver de manera m\'as eficiente el problema planteado, se decidi\'o utilizar la clase canionWarp. Esta clase permite abstraerse de aspectos como la extracci\'on de los par\'ametros que utiliza el programa, as\'i como tambi\'en ir modularizando cada problema, al pensarlo como una funci\'on concreta que deber\'a realizar el cañ\'on.
La clase cañ\'on cuenta con los siguientes m\'etodos y constructores:

\begin{itemize}
	\item \textbf{CanionWarp(int argc, char *argv[])} Crea el cañ\'on utilizando los par\'ametros que se le pasan.
	\item \textbf{void crearMatriz()} Resuelve el sistema que permite calcular la posici\'on enemiga (En realidad s\'olo llama a una funci\'on que la resuelve, ya que; como se mencion\'o, todo el c\'odigo se encuentra modularizado) y calcula la matr\'iz de disparo.
	\item \textbf{escribirArchivo(string destino)} Escribe el archivo de salida con el formato especificado.
\end{itemize}

Adem\'as cuenta con las siguientes variables:
\begin{center}
$\begin{array}{rrrrrr}
\textbf{int} \mathrm{\; dimension} 	& & \textbf{Vector} \mathrm{\; pos\_propia} 		& & \textbf{Matriz} \mathrm{\; matriz\_enemiga} \\
\textbf{int} \mathrm{\; turno} 		& & \textbf{Vector} \mathrm{\; pos\_enemiga} 		& & \textbf{Matriz} \mathrm{\; matriz\_propia} \\
									& & \textbf{Vector} \mathrm{\; impacto\_enemigo} 	& & \textbf{Matriz} \mathrm{\; hilbert}\\
									& & \textbf{Vector} \mathrm{\; impacto\_propio}		& &
\end{array}$
\end{center}

donde Vector y Matriz son redefiniciones de los tipos de datos \texttt{vector<double>} y \texttt{vector<Vector>} respectivamente. Ambas se encuentran en el archivo defs.h.

\begin{subsubsection}{Funci\'on void crearMatriz()}
\par
Esta funci\'on utiliza las estrategias de defensa y de ataque descriptas en el punto anterior. 
\paragraph{}
En el primer turno se toma una posici\'on random como posici\'on enemiga, y en los turnos siguientes se procede a resolver el sistema de ecuaciones
\begin{equation}
matriz\_enemiga \; * \; posicion\_enemiga \, = \, impacto\_enemigo
\end{equation}
usando LU con pivoteo escalado.
\paragraph{}
Se busca la matr\'iz de disparo, resolviendo el sistema
\begin{equation}
matriz\_propia \; * \; posicion\_propia \, = \, posicion\_enemiga
\end{equation}
matriz\_propia es de la forma diag $*$ Hilbert, donde diag es una matr\'iz diagonal representada por un vector, y Hilbert es la matr\'iz de Hilbert de tamaño igual a la dimensi\'on utilizada. Se obtienen los elementos de la diagonal resolviendo el sistema diag * (Hilbert $*$ posicion\_propia) = posicion\_enemiga con divisiones. Luego se multiplica la diagonal por Hilbert y se obtiene la matr\'iz de disparo. Esta matr\'iz de disparo resulta inversible porque la matr\'iz de Hilbert es inversible y al multiplicarla a izquierda por una matr\'iz diagonal, quedan las filas multiplicadas por una constante. Adem\'as estas constantes no son todas nulas porque dependen de la posicion\_propia que no es nula.
\par
Esto puede verse tambi\'en en el c\'odigo de la funci\'on \textbf{void buscarMatriz(Matriz\& matriz, Matriz\& hil, Vector\& pos\_enemigo, Vector\& pos\_propia, int n)} en el archivo sistemas.cpp.
\end{subsubsection}
\end{subsection}

\begin{subsection}{Testing}
\par
Se decidi\'o realizar testing de cada uno de los dos grandes algoritmos del trabajo pr\'actico por separado. Estos son:
\begin{enumerate}
	\item \textsl{PLUPivoteo} para encontrar la posici\'on enemiga, resolviendo sistemas de ecuaciones.
	\item \textsl{buscarMatriz} para disparar, buscando la matr\'iz de disparo.
\end{enumerate}
\par
Los tests para estas funciones son testResolucion y testDisparo respectivamente. 

\par
Adem\'as se teste\'o la correlaci\'on existente entre el n\'umero de condici\'on de la matr\'iz del sistema y la resoluci\'on, en el testCorrelacion.
\begin{subsubsection}{Formato}
\textbf{Para los tests testResolucion y testDisparo}
\par
Para cada valor de $n$ desde $2$ hasta $50$:
\begin{enumerate}
	\item Se generan los vectores y matrices necesarias para los resultados, de tamaño $n$.
	\item Se guarda el valor de $n$ en el archivo de salida (en testDisparo hay varios archivos de salida, en todos ellos se guarda el valor de $n$).
	\item $100$ veces por cada $n$:
	\begin{enumerate}	
		\item Se llenan con n\'umeros random los vectores y matrices necesarios.
		\item Se resuelve el sistema en el caso de testResolucion, y se busca una matr\'iz en el caso de testDisparo. 
		\item Se obtiene la diferencia (distancia euclideana) entre la soluci\'on real y la obtenida. En el caso de testDisparo es la dispancia entre el disparo que se genera usando la matr\'iz encontrada y donde se quer\'ia disparar.
		\item Se guarda la distancia en el archivo de salida. En el caso de testDisparo tambi\'en se guardan las matrices y el n\'umero de condici\'on de cada una de estas matrices. Este n\'umero de condici\'on se obtiene utilizando el programa \textbf{Octave}.
	\end{enumerate}
\end{enumerate}

\textbf{Para el testCorrelacion}
\par
Este test recibe dos archivos de entrada, matrices.in y nroCondicion.in. En matrices.in se encuentran las matrices utilizadas para disparar en el testDisparo, para valores de $n$ fijos. Se seleccionaron los valores de $n = 3, 7, 11$ y $15$. En nroCondicion.in se encuentran los n\'umeros de condici\'on correspondientes a las matrices de matrices.in. Estos n\'umeros de condici\'on tambi\'en provienen de testDisparo.
\paragraph{}
%~ \newpage
Para cada valor de $n = 3, 7, 11, 15$:
\begin{enumerate}
	\item Se generan los vectores necesarios para los resultados, de tamaño $n$.	
	\item $100$ veces por cada $n$:
	\begin{enumerate}	
		\item Se leen la matr\'iz y el n\'umero de condici\'on asociado.
		\item Se llena el vector posicion de forma random.
		\item Se utiliza la matr\'iz le\'ida para el sistema de ecuaciones a resolver.		
		\item Se obtiene la diferencia (distancia euclideana) entre la soluci\'on real y la obtenida. 
		\item Se guarda el n\'umero de condici\'on y la distancia en el archivo de salida. 
	\end{enumerate}
\end{enumerate}

\end{subsubsection}

\begin{subsubsection}{Otros Archivos}
Tambi\'en se realizaron los archivos: 
\begin{itemize}
	\item \textbf{estadistica.cpp} Dado un archivo de la forma $n$ 100 valores por cada $n$, como los generados por testResolucion y testDisparo; y genera estad\'isticas. Por cada $n$ devuelve el m\'aximo, el m\'inimo, el promedio y la mediana. 	
	\item \textbf{graficador.cpp} Dado un archivo de la forma $n$ valor, realiza un gr\'afico, en el que los valores se encuentran en una escala logar\'itmica, usando el programa \textbf{Octave}.
	\item \textbf{graficadorCorrelacion.cpp} Dado un archivo de la forma nro de condicion, distancia, realiza un gr\'afico, en el que las distancias se encuentran en una escala logar\'itmica, usando el programa \textbf{Octave}.
\end{itemize}

\end{subsubsection}

\par 
Los fuentes para realizar los test se encuentran en la carpeta \texttt{/test/} y los datos en la carpeta \texttt{/test/datos}.
\end{subsection}

\begin{subsection}{Batalla Lineal}

\begin{subsubsection}{Código propio vs código propio}
El objetivo de hacer competir el código propio contra si mismo es poder observar el comportamiento del código en una batalla, si concluye la batalla, si logra aplicar las estrategias defensivas y ofensivas correctamente. En la sección \textbf{resultados - tablas} se pueden observar los resultados en forma de tabla incluyendo el ganador de la batalla y la cantidad de turnos jugados. Para obtener los datos se utilizaron valores de n desde 2 hasta 20 inclusive, realizando 100 batallas por cada valor de n.  
\end{subsubsection}

\begin{subsubsection}{Código propio vs otros}
Se obtuvieron archivos ejecutables de otros grupos para poder observar el comportamiento del código propio contra diferentes estrategias de los otros equipos. Al igual que en las batallas contra si mismo se utilizaron valores de n desde 2 hasta 20 inclusive, y los resultados se presentan en la sección \textbf{resultados - tablas} en forma de tabla.
\end{subsubsection}

\begin{subsubsection}{Modalidad}
Para poder realizar las batallas, dado que se utilizó el sistema operativo Linux para la realización del trabajo, se decidió modificar el árbitro para poder ejecutarlo en el sistema elegido. Además para obtener datos se decidió mostrar por cada batalla el valor de n, el ganador y el turno en que terminó. 

\paragraph{}
Para las batallas se crearon dos scripts, \texttt{pelear.sh} y \texttt{resultados.sh} ambos ubicados en la carpeta \texttt{/test}. El script de resultados llama 100 veces por cada n al script de pelear que a su vez ejecuta el arbitro con los contrincantes. El resultado de cada ejecuci\'on se va guardando en un archivo.

\paragraph{}
Todos los resultados obtenidos se encuentran en la carpeta \texttt{/test/datos}.

\paragraph{}
Luego de haber obtenido los datos de n, ganador y turno para cada par de contrincantes, se procedi\'o a realizar estad\'istica sobre estos datos. 
Para esto se utiliz\'o el programa \texttt{estadisticaPeleas} tambi\'en ubicado en la carpeta \texttt{/test}.

\paragraph{}
Los datos relevantes considerados fueron: \\\\
Cantidad de veces y promedio de turno en el que:
\begin{itemize}
	\item ocurre un empate (ambos contrincantes destruyen al otro en el mismo turno).
	\item gana el primer jugador.
	\item gana el segundo jugador.
	\item ocurre un empate por aburrimiento (ning\'un contrincante gana).
\end{itemize}		
	
Como el caso en el que ocurre un empate por aburrimiento siempre se da cuando se llega al turno m\'aximo (50), no se consider\'o el promedio de turno.

\paragraph{}
%~ Los datos se encuentran en la carpeta \texttt{test/datos}, donde \texttt{res} representa la batalla c\'odigo propio vs c\'odigo propio, \texttt{res2} la batalla c\'odigo propio vs primer ejecutable externo, y \texttt{res3} la batalla c\'odigo propio vs segundo ejecutable externo. \\
%~ Para cada uno de estos resultados, los archivos cuya finalizaci\'on es \texttt{Ganadores.out} indica la cantidad de veces mencionada anteriormente, y los que finalizan de la forma \texttt{Turnos.out} contienen el promedio de los turnos de finalizaci\'on de las batallas.
\end{subsubsection}

\end{subsection}

\end{section}
